class Solution {
public:
    int total(int len){
        int digist = 0;
        int cur = 1;
        int count = 9;
        while(cur <= len){
            digist += cur * count;
            cur++;
            count *= 10;
        }
        return digist;
    }
    int findNthDigit(int n) {
        int l = 1;
        int r = 9;
        while(l < r){
            int m = (l + r) / 2;
            if(total(m) < n){
                l = m+1;
            }else{
                r = m;
            }
        }
        
        int d = l;
        int p = total(d-1);
        int rest = n - p - 1;
        
        int start = (int)pow(10,d-1);
        
        int num = start + rest / d;
        int index = rest % d;
        
        int ret = (num / (int)pow(10,d-index-1) ) % 10;
        
        return ret;
    }
};
